\documentclass{ctexart}

\usepackage{ctex}
\usepackage{tikz}
\usetikzlibrary{calc,positioning,shapes.geometric}
\usepackage{url}
\usepackage{graphicx}
\usepackage{float}
\usepackage{xcolor}
\usepackage{color}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{caption}
\usepackage{subfigure}
\usepackage{framed}
\usepackage{booktabs}
\usepackage{makecell}
\usepackage{geometry}
\usepackage{wrapfig}
\usepackage{abstract}
\usepackage{algorithmicx}
\usepackage[ruled]{algorithm}
\usepackage{algpseudocode}
\usepackage{setspace}
\usepackage{bm}
\usepackage{cite}
\usepackage{array}
\usepackage{textcomp}
\usepackage{listings}

\usepackage{geometry}
\geometry{right=2.5cm,left=2.5cm}

\newtheorem{theorem}{定理}

\pagenumbering{arabic}

\begin{document}
\begin{sloppypar}
\title{\vspace{-3cm} \textbf{Homework 2 of Numerical Analysis}}
\author{刘陈若\;$3200104872$\\信息与计算科学2001}
\date{}

\maketitle

\section*{Theoretical questions}
\subsection*{Problem \uppercase\expandafter{\romannumeral1}}
\begin{proof}[\textbf{Solution.}]
It's not difficult to have 
\begin{equation}
p_1(f;x) = -\frac{1}{2}x + \frac{3}{2}
\end{equation}
which passes through points $(1,1)$ and $(2,0.5)$. then we calculate
\begin{equation}
f(x) - p_1(f;x) = \frac{x^2-3x+2}{2x} = \frac{f^{''}(\xi(x))}{2}(x-1)(x-2)
\quad \Longrightarrow \quad f^{''}(\xi(x)) = \frac{1}{x}
\end{equation}
According to \textbf{Theorem 2.7}, noted that this is not a derivation of composite function. Instead we can get
\begin{equation}
\frac{2}{\xi^3(x)} = \frac{1}{x} \quad \Longrightarrow \quad \xi(x)= \sqrt[3]{2x}
\end{equation}

Furthermore，obviously function $\xi(x)= \sqrt[3]{2x}$ is monotonic increasing, and $f^{''}(\xi(x)) = 1/x$ is monotonic decreasing in the interval $[1,2]$. Thus we have, in $[1,2]$,
\begin{equation}
max \ \xi(x) = \sqrt[3]{4} \qquad  min \ \xi(x) = \sqrt[3]{2} \qquad  max \ f^{''}(\xi(x)) = 1
\end{equation}
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral2}}
\begin{proof}[\textbf{Solution.}]
As $f_i \geq 0$, by \textbf{Theorem 2.5}, there exists a unique polynomial $g\in \mathbb{P}_n$ such that $g(x_i) = f^\frac{1}{2}_i$ for $i = 0,1,\dots,n$. 

Set $p(x) = g^2(x)$, then it's easy to show that $p \in \mathbb{P}^+_{2n}$ as $g^2(x)\geq 0$. Additionally, $p(x_i) = g^2(x_i) = f_i$ for $i = 0,1,\dots,n$. Therefore we successfully find the proper $p$.
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral3}}
\begin{proof}[\textbf{Solution.}]
For $n=1$, the equation reduces to $f[t,t+1] = (e-1)e^t$, which can be easily concluded as 
\begin{equation}
f[t,t+1] = \frac{f[t+1]-f[t]}{t+1-t} = e^{t+1} - e^t= (e-1)e^t    
\end{equation}

Suppose the equation holds. For the inductive step, we have
\begin{equation}
\begin{aligned}
    f[t,t+1,\dots,t+n+1] &= \frac{f[t+1,\dots,t+1+n]-f[t,\dots,t+n]}{n+1} \\
    &= \frac{\frac{(e-1)^n}{n!}e^{t+1} - \frac{(e-1)^n}{n!}e^t}{n+1} \\
    &= \frac{(e-1)^n}{(n+1)!}e^t(e-1) \\
    &= \frac{(e-1)^{n+1}}{(n+1)!}e^t
\end{aligned}      
\end{equation}
thus finishing the proof.

Furthermore, if $t=0$, we have
\begin{equation}
    f[0,1,\dots,n] = \frac{(e-1)^n}{n!} = \frac{1}{n!}f^{(n)}(\xi)
\end{equation}
Similar to Problem \uppercase\expandafter{\romannumeral1}, that implies 
\begin{equation}
    e^{\xi(n)} = (e-1)^n \quad \Longrightarrow \quad \xi(n)=nln(e-1)
\end{equation}

As $ln(e-1)>\frac{1}{2}$, $\xi>\frac{n}{2}$ respectively.
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral4}}
\begin{proof}[\textbf{Solution.}]
By $Definition 2.18$, we can construct the following table divided difference,

\begin{table}[H]
\renewcommand{\arraystretch}{1.2}
 \centering
 \setlength{\tabcolsep}{0.3cm}{
\begin{tabular}{c|cccc}
     0 & 5  \\
     1 & 3 & -2 \\
     3 & 5 & 1 & 1 \\
     4 & 12 & 7 & 2 & 0.25 \\
\end{tabular}}
\end{table}
By $Definition 2.14$, the interpolating polynomial is generated from the main diagonal and the first column of the above table as follows.
\begin{equation}
    p_3(f;x) = 5 - 2x +x(x-1) +0.25x(x-1)(x-3)
\end{equation}

Furthermore, calculating the first-order derivative of $p_3$ we have
\begin{equation}
    p^{'}_{3}(f;x) = 0.75x^2-2.25
\end{equation}
Then we can find its root in the interval $(1,3)$, which is $\sqrt{3}$. Therefore we can estimate the location of the minimum as $x_{min} = \sqrt{3}$.  
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral5}}
\begin{proof}[\textbf{Solution.}]
The Hermite interpolation problem can be expressed as
\begin{equation}
    f_0 = 0, \quad f_1 = 1, \quad f'_1 = 7, \quad f^{''}_1 = 42, \quad f_2 = 128, \quad f'_2 = 448
\end{equation}
And the table of divided difference has the form
\begin{table}[H]
\renewcommand{\arraystretch}{1.2}
 \centering
 \setlength{\tabcolsep}{0.3cm}{
\begin{tabular}{c|cccccc}
     0 & 0  \\
     1 & 1 & 1 \\
     1 & 1 & 7 & 6 \\
     1 & 1 & 7 & 21 & 15 \\
     2 & 128 & 127 & 120 & 99 & 42\\
     2 & 128 & 448 & 321 & 201 & 102 & 30\\
\end{tabular}}
\end{table}
The table shows that $f[0,1,1,1,2,2] = 30$.

Furthermore, we know that the divided difference is expressible in terms of $\frac{1}{5!}f^{(5)}(\xi)$. Therefore, by solving the equation
\begin{equation}
    \frac{1}{5!}f^{(5)}(\xi) = 30
\end{equation}
we have $\xi = \sqrt{\frac{10}{7}}$.
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral6}}
\begin{proof}[\textbf{Solution.}]
Similar to the question above, the table of the divided differences has the form
\begin{table}[H]
\renewcommand{\arraystretch}{1.2}
 \centering
 \setlength{\tabcolsep}{0.3cm}{
\begin{tabular}{c|ccccc}
     0 & 1  \\
     1 & 2 & 1 \\
     1 & 2 & -1 & -2\\
     3 & 0 & -1 & 0 & $\frac{2}{3}$ \\
     3 & 0 & 0 & $\frac{1}{2}$ & $\frac{1}{4}$ & $-\frac{5}{36}$\\
\end{tabular}}
\end{table}
so we know from the table that
\begin{equation}
    p_4(f;x) = 1 + x - 2x(x-1) + \frac{2}{3}x(x-1)^2 - \frac{5}{36}x(x-1)^2(x-3)
\end{equation}
Set $x=2$ in $p_4$, we estimate $f(2)$ as $p_4(f;2) = \frac{11}{18}$.

Furthermore, according to \textbf{Theorem 2.35}, we have
\begin{equation}
    R_4(f;x) = \frac{f^{(5)}(\xi)}{5!}x(x-1)^2(x-3)^2
\end{equation}
So, using the condition $|f^{(5)}(x)|\leq M$ on $[0,3]$, we have
\begin{equation}
    |R_4(f;2)| = |\frac{1}{60}f^{(5)}(\xi)| \leq \frac{M}{60}
\end{equation}
Hence we estimate the maximum error of the above answer as $\frac{M}{60}$.
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral7}}
\begin{proof}[\textbf{Solution.}]
We prove these by inductions.

For the first equation, when $k=0$, obviously $LHS = RHS = f(x)= f(x_0)$ as $0!=1$.
Suppose the equation holds. For the inductive step, we have
\begin{equation}
\begin{aligned}
    \Delta^{k+1}f(x) &= \Delta^kf(x+h) - \Delta^kf(x) \\
    &= k!h^k(f[x_1,x_2,\dots,x_{k+1}] - f[x_0,x_1,\dots,x_k]) \\
    &= k!h^k(x_{k+1} - x_0)f[x_0,x_1,\dots,x_{k+1}]\\
    &= (k+1)!h^{k+1}f[x_0,x_1,\dots,x_{k+1}]
\end{aligned}      
\end{equation}
thus finishing the proof.

For the second equation, when $k=0$, obviously $LHS = RHS = f(x)= f(x_0)$ as $0!=1$.
Suppose the equation holds. For the inductive step, we have
\begin{equation}
\begin{aligned}
    \nabla^{k+1}f(x) &= \nabla^kf(x) - \nabla^kf(x-h) \\
    &= k!h^k(f[x_0,x_{-1},\dots,x_{-k}] - f[x_{-1},x_{-2},\dots,x_{-k-1}]) \\
    &= k!h^k(x_0 - x_{-k-1})f[x_0,x_{-1},\dots,x_{-k-1}]\\
    &= (k+1)!h^{k+1}f[x_0,x_{-1},\dots,x_{-k-1}]
\end{aligned}      
\end{equation}
thus finishing the proof.
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral8}}
\begin{proof}[\textbf{Solution.}]
Using the definition of partial derivative, the continuity of divided difference, \textbf{Corollary 2.15} and \textbf{Theorem 2.17}, we have
\begin{equation}
\begin{aligned}
\frac{\partial}{\partial x_0}f[x_0,x_1,\dots,x_n] &= \lim_{h \rightarrow 0}\frac{f[x_0+h, x_1,\dots,x_n]- f[x_0,x_1,\dots,x_n]}{h} \\
&= \lim_{h \rightarrow 0}\frac{f[x_1,\dots,x_n,x_0+h]- f[x_0,x_1,\dots,x_n]}{h} \\
&= \lim_{h \rightarrow 0}f[x_0,x_1,\dots,x_n,x_0+h] \\
&= \lim_{h \rightarrow 0}f[x_0,x_0+h,x_1,\dots,x_n] \\
&= f[x_0,x_0,x_1,\dots,x_n]
\end{aligned}
\end{equation}
thus finishing the proof. Similarly, for any $x_i$ ($i = 1,2,\dots,n$), we have
\begin{equation}
\begin{aligned}
\frac{\partial}{\partial x_i}f[x_0,x_1,\dots,x_n] &= \lim_{h \rightarrow 0}\frac{f[x_0, x_1,\dots,x_i+h,\dots,x_n]- f[x_0,x_1,\dots,x_i,\dots,x_n]}{h} \\
&= \lim_{h \rightarrow 0}\frac{f[x_0,x_1,\dots,x_{i-1},x_{i+1},\dots,x_i+h]- f[x_i,x_0,x_1,\dots,x_{i-1},x_{i+1},\dots,x_n]}{h} \\
&= \lim_{h \rightarrow 0}f[x_i,x_0,x_1,\dots,x_{i-1},x_{i+1},\dots,x_n,x_i+h] \\
&= \lim_{h \rightarrow 0}f[x_0,x_1,\dots,x_{i-1},x_i,x_i+h,x_{i+1},\dots,x_n] \\
&= f[x_0,x_1,\dots,x_i,x_i,\dots,x_n]
\end{aligned}
\end{equation}
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral9}}
\begin{proof}[\textbf{Solution.}]
Without loss of generality, we translate interval $[a,b]$ to $[-m,m]$, where $m$ satisfies $m = (b-a)/2$.

From Chebyshev Theorem we know
\begin{equation}
    min \mathop{max}\limits_{x \in [-1,1]} |a_0x^n+a_1x^{n-1}+\dots+a_n| = \frac{|a_0|}{2^{n-1}}
\end{equation}
Therefore, by a linear transformation $x \rightarrow mx$, we have
\begin{equation}
    min \mathop{max}\limits_{x \in [-m,m]} |a_0x^n+a_1x^{n-1}+\dots+a_n| = \frac{|a_0|m^n}{2^{n-1}}
\end{equation}
And from this we finally determine
\begin{equation}
    min \mathop{max}\limits_{x \in [a,b]} |a_0x^n+a_1x^{n-1}+\dots+a_n| = \frac{|a_0|(\frac{b-a}{2})^n}{2^{n-1}}=\frac{|a_0|(b-a)^n}{2^{2n-1}}
\end{equation}
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral10}}
\begin{proof}[\textbf{Solution.}]
By \textbf{Theorem 2.42}, $T_n(x)$ assumes its extrema $n+1$ times at points $x'_k$ defined in (2.44) in textbook. Suppose $||\hat{p_n}||_\infty \leq ||p||_\infty$ does not hold. Then it implies that
\begin{equation}
    \exists p \in \mathbb{P}^a_n \quad s.t. \quad ||p||_\infty \leq ||\hat{p_n}||_\infty
\end{equation}
Consider the polynomial $Q(x)= \hat{p_n}(x) - p(x)$, then
\begin{equation}
    Q(x'_k) = \frac{(-1)^k}{T_n(a)} - p(x'_k) \quad k = 0,1,\dots,n
\end{equation}
By the condition $||p||_\infty \leq ||\hat{p_n}||_\infty$, $Q(x)$ has alternating signs at these $n+1$ points. Hence $Q(x)$ must have $n$ zeros.
Additionally, $Q(a) = 1-1=0$, so $Q$ has at least $n+1$ zeros.

However, by the construction of $Q(x)$, the degree of $Q(x)$ is at most $n$. Therefore, $Q(x)\equiv0$, which means $p(x) = \hat{p_n}(x)$. This is a contradiction to the assumption, thus finishing the proof.
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral11}}
\begin{proof}[\textbf{Solution.}]
Firstly, based on Binomial expansion we have
\begin{equation}
    \sum_{k=0}^n b_{n,k}(t) = (t+1-t)^n = 1
\end{equation}
Secondly, based on the equation above, we have
\begin{equation}
\begin{aligned}
    \sum_{k=0}^n \frac{k}{nt}b_{n,k}(t) &=  \sum_{k=1}^n \frac{k}{nt}b_{n,k}(t) \\
    & = \sum_{k=1}^n \frac{kn!}{nt(n-k)!k!}t^k(1-t)^{n-k} \\
    & = \sum_{k=1}^n C^{k-1}_{n-1}t^{k-1}(1-t)^{(n-1)-(k-1)} \\
    & = \sum_{k=1}^n b_{n-1,k-1}(t) = \sum_{k=0}^n b_{n-1,k}(t) \\
    & = 1
\end{aligned}
\end{equation}
Therefore, $\sum_{k=0}^n kb_{n,k}(t) = nt$.

Thirdly, similar with the proof of (2.50c), we first have
\begin{equation}
\begin{aligned}
    \sum_{k=0}^n \frac{k(k-1)}{n(n-1)t^2}b_{n,k}(t) &=  \sum_{k=2}^n \frac{k(k-1)}{n(n-1)t^2}b_{n,k}(t) \\
    & = \sum_{k=2}^n \frac{k(k-1)n!}{n(n-1)t^2(n-k)!k!}t^k(1-t)^{n-k} \\
    & = \sum_{k=2}^n C^{k-2}_{n-2}t^{k-2}(1-t)^{(n-2)-(k-2)} \\
    & = \sum_{k=2}^n b_{n-2,k-2}(t) = \sum_{k=0}^n b_{n-2,k}(t) \\
    & = 1
\end{aligned}
\end{equation}
Therefore, $\sum_{k=0}^n k(k-1)b_{n,k}(t) = n(n-1)t^2$. Then, according to all the euqations above, we have
\begin{equation}
\begin{aligned}
    \sum_{k=0}^n (k-nt)^2b_{n,k}(t) &=  \sum_{k=0}^n [k(k-1) + k -2nkt +n^2t^2]b_{n,k}(t) \\
    & = n(n-1)t^2 + nt -2n^2t^2 + n^2t^2 \\
    & = nt - nt^2 = nt(1-t)
\end{aligned}
\end{equation}

\end{proof}

\end{sloppypar}
\end{document}
